﻿#include <iostream>
#include <unordered_map>
#include "BinaryTree.h"

using namespace std;

static void recur(const int* pre, const int* in, unordered_map<int, int>& inPosMap, int* post, int preLeft, int preRight, int inLeft, int inEnd, int postLeft, int postRight)
{
    if (postLeft > postRight) return;

    if (postLeft == postRight)
    {
        post[postLeft] = pre[preLeft];
        return;
    }

    post[postRight] = pre[preLeft];
    int inPos = inPosMap[pre[preLeft]];
    int len = inPos - inLeft;
    recur(pre, in, inPosMap, post, preLeft + 1, preLeft + len, inLeft, inLeft + len - 1, postLeft, postLeft + len - 1);
    recur(pre, in, inPosMap, post, preLeft + len + 1, preRight, inLeft + len + 1, inEnd, postLeft + len, postRight - 1);
}

// 已知一颗二叉树中没有重复节点，并且给定了这棵树的中序遍历数组和先序遍历数组，返回后续遍历数组。
// 比如给定:
// int[] pre = [1, 2, 4, 5, 3, 6, 7];
// int[] in = [4, 2, 5, 1, 6, 3, 7];
// 返回:
// [4, 5, 2, 6, 7, 3, 1]
//
//思路：
// 使用递归
// 1. 先声明一个和pre同等长度的数组pos, [0, 0, 0, 0, 0, 0, 0]
// 2. 观察pre，其第一个元素表示根节点，那必然是pos的最后一个节点。
// pos = [0, 0, 0, 0, 0, 0, 1]
// 3. 1在in数组中的位置，该位置左侧为左树的元素，右侧为右树的元素，由此切分递归完成整个pos数组
// 比如根节点是1, 1在in数组的第3号位置，则in数组1的左侧的[4, 2, 5]即为左树节点，pre的1后面3个元素也是左树节点，
// pos的前3个节点也是左树节点。
int main_PostOrderFromPreOrderAndInOrder()
{
    int pre[] = { 11, 7, 3, 2, 4, 9, 8, 10, 15, 12, 18, 16 };
    int in[] = { 2, 3, 4, 7, 8, 9, 10, 11, 12, 15, 16, 18 };
    size_t size = sizeof(pre) / sizeof(int);
    unordered_map<int, int> inPosMap;
    for (int i = 0; i < size; i++)
    {
        inPosMap.insert({ in[i], i });
    }

    int* post = (int*)malloc(size * sizeof(int));
    memset(post, 0, size * sizeof(int));
    recur(pre, in, inPosMap, post, 0, size - 1, 0, size - 1, 0, size - 1);

    for (int i = 0; i < size; i++)
    {
        printf("%d,", post[i]);
    }

    printf("\n");
    free(post);
    return 0;
}